perm filename QUEENS.FAI[1,BGB] blob
sn#057498 filedate 1973-08-10 generic text, type T, neo UTF8
COMMENT ⊗ VALID 00010 PAGES
RECORD PAGE DESCRIPTION
00001 00001
00003 00002 TITLE QUEENS PUZZLE PROBLEM - 1 DECEMBER 1972.
00005 00003 TABLES OF THE GROUP OF SYMMETRIES OF A SQUARE.
00007 00004 T4:
00009 00005 One Queen Attack Table - 64 boards.
00011 00006 MAKE ONE QUEEN ATTACK TABLE.
00013 00007 MAKE TWO QUEEN ATTACK TABLE - UNORDERED PAIR OF QUEENS.
00014 00008 MAKE FIVE QUEEN ATTACKS - RECORD FULL BOARD COVERAGE.
00016 00009 IGNORE REDUNDANT SOLUTIONS DUE TO BOARD SYMMETRIES.
00018 00010 MAIN EXECUTION.
00019 ENDMK
⊗;
TITLE QUEENS PUZZLE PROBLEM - 1 DECEMBER 1972.
;ACCUMULATORS
Q1←7
Q2←10
R←11 ↔ ROW←12
C←13 ↔ COL←14
K←14
CNT←15
I←16
J←17
; ALTERNATE PDP-10 MNEMONICS.
OPDEF LIP[HLR]↔OPDEF LAP[HRR]↔OPDEF DIP[HRLM]
OPDEF DAP[HRRM]↔OPDEF CAR[HLRZ]↔OPDEF CDR[HRRZ]
OPDEF DIPZ[HRLZM]↔OPDEF DAPZ[HRRZM]↔OPDEF ZIP[HRRZS]
OPDEF ZAP[HLLZS]↔OPDEF WIP[HRROS]↔OPDEF WAP[HRRZS]
OPDEF NIP[HLRE]↔OPDEF NAP[HRRE]↔OPDEF NIM[HRREI]
OPDEF LAC[MOVE]↔OPDEF DAC[MOVEM]↔OPDEF SLAC[MOVS]
OPDEF GO[JRST]↔OPDEF LACI[MOVEI]↔OPDEF SLACI[MOVSI]
OPDEF LAPI[HRRI]↔OPDEF LIPI[HRLI]↔OPDEF LACN[MOVN]
;YE VERY OLDE TYPE OUT DECIMAL NUMBER ROUTINE.
ONUM: IDIVI 1,12↔PUSH 17,2↔SKIPE 1↔PUSHJ 17,ONUM
POP 17,1↔ADDI 1,60↔OUTCHR 1↔POPJ 17,
PDL: BLOCK 100
;TABLES OF THE GROUP OF SYMMETRIES OF A SQUARE.
;T0:
;00 ;01 ;02 ;03 ;04 ;05 ;06 ;07
;10 ;11 ;12 ;13 ;14 ;15 ;16 ;17
;20 ;21 ;22 ;23 ;24 ;25 ;26 ;27
;30 ;31 ;32 ;33 ;34 ;35 ;36 ;37
;40 ;41 ;42 ;43 ;44 ;45 ;46 ;47
;50 ;51 ;52 ;53 ;54 ;55 ;56 ;57
;60 ;61 ;62 ;63 ;64 ;65 ;66 ;67
;70 ;71 ;72 ;73 ;74 ;75 ;76 ;77
T1:
07 ↔06 ↔05 ↔04 ↔03 ↔02 ↔01 ↔00
17 ↔16 ↔15 ↔14 ↔13 ↔12 ↔11 ↔10
27 ↔26 ↔25 ↔24 ↔23 ↔22 ↔21 ↔20
37 ↔36 ↔35 ↔34 ↔33 ↔32 ↔31 ↔30
47 ↔46 ↔45 ↔44 ↔43 ↔42 ↔41 ↔40
57 ↔56 ↔55 ↔54 ↔53 ↔52 ↔51 ↔50
67 ↔66 ↔65 ↔64 ↔63 ↔62 ↔61 ↔60
77 ↔76 ↔75 ↔74 ↔73 ↔72 ↔71 ↔70
T2:
70 ↔71 ↔72 ↔73 ↔74 ↔75 ↔76 ↔77
60 ↔61 ↔62 ↔63 ↔64 ↔65 ↔66 ↔67
50 ↔51 ↔52 ↔53 ↔54 ↔55 ↔56 ↔57
40 ↔41 ↔42 ↔43 ↔44 ↔45 ↔46 ↔47
30 ↔31 ↔32 ↔33 ↔34 ↔35 ↔36 ↔37
20 ↔21 ↔22 ↔23 ↔24 ↔25 ↔26 ↔27
10 ↔11 ↔12 ↔13 ↔14 ↔15 ↔16 ↔17
00 ↔01 ↔02 ↔03 ↔04 ↔05 ↔06 ↔07
T3:
77 ↔76 ↔75 ↔74 ↔73 ↔72 ↔71 ↔70
67 ↔66 ↔65 ↔64 ↔63 ↔62 ↔61 ↔60
57 ↔56 ↔55 ↔54 ↔53 ↔52 ↔51 ↔50
47 ↔46 ↔45 ↔44 ↔43 ↔42 ↔41 ↔40
37 ↔36 ↔35 ↔34 ↔33 ↔32 ↔31 ↔30
27 ↔26 ↔25 ↔24 ↔23 ↔22 ↔21 ↔20
17 ↔16 ↔15 ↔14 ↔13 ↔12 ↔11 ↔10
07 ↔06 ↔05 ↔04 ↔03 ↔02 ↔01 ↔00
T4:
70 ↔60 ↔50 ↔40 ↔30 ↔20 ↔10 ↔00
71 ↔61 ↔51 ↔41 ↔31 ↔21 ↔11 ↔01
72 ↔62 ↔52 ↔42 ↔32 ↔22 ↔12 ↔02
73 ↔63 ↔53 ↔43 ↔33 ↔23 ↔13 ↔03
74 ↔64 ↔54 ↔44 ↔34 ↔24 ↔14 ↔04
75 ↔65 ↔55 ↔45 ↔35 ↔25 ↔15 ↔05
76 ↔66 ↔56 ↔46 ↔36 ↔26 ↔16 ↔06
77 ↔67 ↔57 ↔47 ↔37 ↔27 ↔17 ↔07
T5:
77 ↔67 ↔57 ↔47 ↔37 ↔27 ↔17 ↔07
76 ↔66 ↔56 ↔46 ↔36 ↔26 ↔16 ↔06
75 ↔65 ↔55 ↔45 ↔35 ↔25 ↔15 ↔05
74 ↔64 ↔54 ↔44 ↔34 ↔24 ↔14 ↔04
73 ↔63 ↔53 ↔43 ↔33 ↔23 ↔13 ↔03
72 ↔62 ↔52 ↔42 ↔32 ↔22 ↔12 ↔02
71 ↔61 ↔51 ↔41 ↔31 ↔21 ↔11 ↔01
70 ↔60 ↔50 ↔40 ↔30 ↔20 ↔10 ↔00
T6:
00 ↔10 ↔20 ↔30 ↔40 ↔50 ↔60 ↔70
01 ↔11 ↔21 ↔31 ↔41 ↔51 ↔61 ↔71
02 ↔12 ↔22 ↔32 ↔42 ↔52 ↔62 ↔72
03 ↔13 ↔23 ↔33 ↔43 ↔53 ↔63 ↔73
04 ↔14 ↔24 ↔34 ↔44 ↔54 ↔64 ↔74
05 ↔15 ↔25 ↔35 ↔45 ↔55 ↔65 ↔75
06 ↔16 ↔26 ↔36 ↔46 ↔56 ↔66 ↔76
07 ↔17 ↔27 ↔37 ↔47 ↔57 ↔67 ↔77
T7:
07 ↔17 ↔27 ↔37 ↔47 ↔57 ↔67 ↔77
06 ↔16 ↔26 ↔36 ↔46 ↔56 ↔66 ↔76
05 ↔15 ↔25 ↔35 ↔45 ↔55 ↔65 ↔75
04 ↔14 ↔24 ↔34 ↔44 ↔54 ↔64 ↔74
03 ↔13 ↔23 ↔33 ↔43 ↔53 ↔63 ↔73
02 ↔12 ↔22 ↔32 ↔42 ↔52 ↔62 ↔72
01 ↔11 ↔21 ↔31 ↔41 ↔51 ↔61 ↔71
00 ↔10 ↔20 ↔30 ↔40 ↔50 ↔60 ↔70
;One Queen Attack Table - 64 boards.
QAT1: BLOCK =64
QAT2: BLOCK =64
;Two Queens Attack Table - 2016 boards.
QQAT1: BLOCK =2016
QQAT2: BLOCK =2016
QQL1: BLOCK =2016
QQL2: BLOCK =2016
;Scratch Attack Table - 2016 boards.
SAT1: BLOCK =2016
SAT2: BLOCK =2016
SAT3: 0
;Column attack table - 8 boards.
CAT: 1001001001B28↔1001001001B28 ;COL 0.
1001001001B29↔1001001001B29 ;COL 1.
1001001001B30↔1001001001B30 ;COL 2.
1001001001B31↔1001001001B31 ;COL 3.
1001001001B32↔1001001001B32 ;COL 4.
1001001001B33↔1001001001B33 ;COL 5.
1001001001B34↔1001001001B34 ;COL 6.
1001001001B35↔1001001001B35 ;COL 7.
;Row Attack Table - 8 boards.
RAT: 377B8↔0 ;ROW 0.
377B17↔0 ;ROW 1.
377B26↔0 ;ROW 2.
377B35↔0 ;ROW 3.
0↔377B8 ;ROW 4.
0↔377B17 ;ROW 5.
0↔377B26 ;ROW 6.
0↔377B35 ;ROW 7.
;Byte pointer to column 7 of each row.
ROWPTR: POINT 1,Q1,8 ↔ POINT 1,Q1,17 ;ROWS 0 & 1.
POINT 1,Q1,26↔ POINT 1,Q1,35 ;ROWS 2 & 3.
POINT 1,Q2,8 ↔ POINT 1,Q2,17 ;ROWS 4 & 5.
POINT 1,Q2,26↔ POINT 1,Q2,35 ;ROWS 6 & 7.
;Byte pointer P-bits of each column.
COLPTR: 7B5↔6B5↔5B5↔4B5
3B5↔2B5↔1B5↔0
;Make a bit pointer to a square of the board.
DEFINE MKPTR{LAC 1,ROWPTR(R)↔ADD 1,COLPTR(C)}
;MAKE ONE QUEEN ATTACK TABLE.
MKQAT: 0
LACI I,100↔LACI ROW,7↔LACI COL,7↔SOS I
LSH ROW,1↔LAC Q1,RAT(ROW)↔LAC Q2,RAT+1(ROW)↔LSH ROW,-1
LSH COL,1↔IOR Q1,CAT(COL)↔IOR Q2,CAT+1(COL)↔LSH COL,-1
LACI 1
LAC R,ROW↔LAC C,COL↔JSR NE
LAC R,ROW↔LAC C,COL↔JSR NW
LAC R,ROW↔LAC C,COL↔JSR SW
LAC R,ROW↔LAC C,COL↔JSR SE
LAC R,ROW↔LAC C,COL↔MKPTR↔SETZ↔DPB 0,1
DAC Q1,QAT1(I)↔DAC Q2,QAT2(I)
SOJGE COL,MKQAT+4
SOJGE ROW,MKQAT+3
GO @MKQAT
;NORTH EAST ATTACK: R-1,C+1.
NE: 0
SOSGE R↔GO@NE
AOS C↔CAIN C,8↔GO @NE
MKPTR↔DPB 0,1↔GO NE+1
;NORTH WEST ATTACK: R-1,C-1.
NW: 0
SOSGE R↔GO@NW
SOSGE C↔GO@NW
MKPTR↔DPB 0,1↔GO NW+1
;SOUTH WEST ATTACK: R+1,C-1.
SW: 0
AOS R↔CAIN R,8↔GO@SW
SOSGE C↔GO@SW
MKPTR↔DPB 0,1↔GO SW+1
;SOUTH EAST ATTACK: R+1,C+1.
SE: 0
AOS R↔CAIN R,8↔GO@SE
AOS C↔CAIN C,8↔GO@SE
MKPTR↔DPB 0,1↔GO SE+1
;MAKE TWO QUEEN ATTACK TABLE - UNORDERED PAIR OF QUEENS.
MKQQAT: 0
SETZ I,
SETZ 1,
L1: SETZ 2,
L2: CAML 1,2↔GO L3
LAC QAT1(1)↔IOR QAT1(2)↔DAC QQAT1(I)
LAC QAT2(1)↔IOR QAT2(2)↔DAC QQAT2(I)
DAC 1,QQL1(I)
DAC 2,QQL2(I)
AOS I
L3: AOS 2↔CAIE 2,100↔GO L2
AOS 1↔CAIE 1,100↔GO L1
GO @MKQQAT
;MAKE A PARTIAL THREE QUEEN ATTACK TABLE.
;ARGUMENT - THIRD QUEEN'S POSITION NUMBER - AC1.
MK3QAT:0
LAC[XWD QQAT1,SAT1]↔BLT SAT3-1
LAC Q1,QAT1(K)
LAC Q2,QAT2(K)
IOR Q1,[400400400400] ;SET EMPTY BITS.
IOR Q2,[400400400400]
LACI I,=2016
IORM Q1,SAT1(I)
IORM Q2,SAT2(I)
SOJGE I,.-2
GO @MK3QAT
;MAKE FIVE QUEEN ATTACKS - RECORD FULL BOARD COVERAGE.
MK5QAT: 0
SETZ CNT,
SETZ I,
M1: SETZ J,
CAML K,QQL1(I)↔GO M4
LAC 0,QQL2(I)
M2: CAML 0,QQL1(J)↔GO M3
SETCM Q1,SAT1(I)↔ANDCM Q1,SAT1(J)↔JUMPN Q1,M3
SETCM Q2,SAT2(I)↔ANDCM Q2,SAT2(J)↔JUMPN Q2,M3
;DETECT SOLUTIONS THAT ARE REDUNDANT BECAUSE THEY CAN BE
;MAPPED INTO A FORM WITH A QUEEN LESS THAN K.
LAC 1,K↔LSH 1,6
IOR 1,QQL1(I)↔JSR SYMM↔LSH 1,6
IOR 1,QQL2(I)↔JSR SYMM↔LSH 1,6
IOR 1,QQL1(J)↔JSR SYMM↔LSH 1,6
IOR 1,QQL2(J)↔JSR SYMM
;DETECT SOLUTIONS THAT ARE REDUNDANT BECAUSE THEY MAP
;A QUEEN INTO POSITION K AND HAVE ALREADY BEEN RECORDED.
JUMPE CNT,M5↔DAC 1,10
JSR SYMM2↔ROT 1,-6
JSR SYMM2↔ROT 1,-6
JSR SYMM2↔ROT 1,-6
JSR SYMM2↔LSH 1,-6
JSR SYMM2↔LAC 1,10
;OUTPUT A SOLUTION TO THE BUFFER.
M5: AOS 2,SUBTOTAL#
AOS CNT
M0: DAC 1,BUFFER(2)
M3: AOS J↔CAIE J,=2016↔GO M2
M4: AOS I↔CAIE I,=2016↔GO M1
GO @MK5QAT
BUFFER: BLOCK 5000
;IGNORE REDUNDANT SOLUTIONS DUE TO BOARD SYMMETRIES.
; π/2 ROTATIONS; DIAGONAL, HORIZONTAL & VERTICAL REFLECTIONS.
SYMM: 0
LAC 2,1
ANDI 2,77
FOR @' I←1,7{
CAMLE K,T'I(2)↔GO M3}
GO@SYMM
SYMM2: 0
LAC 2,1
ANDI 2,77
FOR @' I←1,7{
CAMN K,T'I(2)↔JSP 12,SYMT'I}
GO @SYMM2
;TRANSFORM THE SOLUTION IN AC-10.
FOR @' I←1,7{
SYMT'I:
LAC 11,[POINT 6,10,5]
ILDB 3,11↔LAC 3,T'I(3)
ILDB 4,11↔LAC 4,T'I(4)
ILDB 5,11↔LAC 5,T'I(5)
ILDB 6,11↔LAC 6,T'I(6)
ILDB 7,11↔LAC 7,T'I(7)
GO SYM3}
;GET THE TRANSFORMED SOLUTION INTO CANONICAL FORM.
SYM3: CAML 3,4↔EXCH 3,4↔CAML 3,5↔EXCH 3,5
CAML 3,6↔EXCH 3,6↔CAML 3,7↔EXCH 3,7
CAML 4,5↔EXCH 4,5
CAML 4,6↔EXCH 4,6↔CAML 4,7↔EXCH 4,7
CAML 5,6↔EXCH 5,6↔CAML 5,7↔EXCH 5,7
CAML 6,7↔EXCH 6,7
LSH 3,6↔IOR 3,4↔LSH 3,6↔IOR 3,5
LSH 3,6↔IOR 3,6↔LSH 3,6↔IOR 3,7
;SEARCH BACK THROUGH THE BUFFER FOR A MATCH.
LAC 4,CNT↔LAC 5,SUBTOTAL
CAMN 3,BUFFER(5)↔GO M3↔SOS 5
SOJG 4,.-3↔GO(12)
;MAIN EXECUTION.
SA: JSR MKQAT
JSR MKQQAT
SETZM TOTAL#
DEFINE CALLQ $(Q){
LACI K,Q↔JSR MK3QAT↔JSR MK5QAT
DAC CNT,CNT$Q#↔ADDM CNT,TOTAL
JSR OUTNUM}
CALLQ(23)
CALLQ(22)
CALLQ(13)
CALLQ(12)
CALLQ(11)
CALLQ(03)
CALLQ(02)
CALLQ(01)
CALLQ(00)
;OUTPUT FILE OF SOLUTIONS.
LAC SUBTOTAL↔DAC BUFFER
INIT 1,17↔SIXBIT/DSK/↔0↔HALT
ENTER 1,[SIXBIT/QFILE/↔0↔0↔0]↔JFCL
OUT 1,[IOWD 5000,BUFFER↔0]↔JFCL↔RELEASE 1,
CALLI 12
OUTNUM: 0
OUTSTR[BYTE(7)15,12]↔LACI 17,PDL
LAC 1,CNT↔PUSHJ 17,ONUM↔OUTCHR[9]
LAC 1,SUBTOTAL↔PUSHJ 17,ONUM↔OUTCHR[9]
LAC 1,TOTAL↔PUSHJ 17,ONUM
GO @OUTNUM
END SA